import random


def partition(arr, L, R):
    l = L - 1
    r = R
    while L != r:
        if arr[L] < arr[R]:
            l += 1
            arr[L], arr[l] = arr[l], arr[L]
            L += 1
        elif arr[L] > arr[R]:
            r -= 1
            arr[L], arr[r] = arr[r], arr[L]
        else:
            L += 1
    arr[R], arr[r] = arr[r], arr[R]
    return l, r + 1


def quick_sort(arr, L, R):
    if L < R:
        rand = random.randint(L, R)
        arr[rand], arr[R] = arr[R], arr[rand]
        l, r = partition(arr, L, R)
        quick_sort(arr, L, l)
        quick_sort(arr, r, R)


if __name__ == "__main__":
    arr = [4, 2, 6, 1, 9, 5]
    quick_sort(arr, 0, len(arr)-1)
    print(arr)
